/*
 * @Author: dadadaXU 1413107032@qq.com
 * @Date: 2025-02-19 11:04:41
 * @LastEditors: dadadaXU 1413107032@qq.com
 * @LastEditTime: 2025-02-20 13:40:20
 * @FilePath: \LeetCode\543.二叉树的直径.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
/*
 * @lc app=leetcode.cn id=543 lang=cpp
 *
 * [543] 二叉树的直径
 *
 * 方法1：左子树半径 + 右子树半径 -> 深度
 * - 理解偏差：一组测试用例不通过（见下）
 * 
 * 官方题解：根节点 = deepL + deepR + 1(缺失)
 * - 边数 = 节点数(深度) - 1
 */

#include "BinaryTree.hpp"

// @lc code=start

class Solution
{
public:
    // int longestRadiusBT(TreeNode *root) // 二叉树的较长的一边（半径）
    // {
    //     if (root == nullptr)
    //         return 0;

    //     int leftRadius = longestRadiusBT(root->left);
    //     int rightRadius = longestRadiusBT(root->right);

    //     if (leftRadius > rightRadius)
    //         return leftRadius + 1;
    //     else
    //         return rightRadius + 1;
    // }

    int diameter = 1;

    int maxDepth(TreeNode *root)
    {
        if (root == nullptr)
            return 0;

        int leftTreeHigh = maxDepth(root->left);
        int rightTreeHigh = maxDepth(root->right);

        diameter = std::max(leftTreeHigh + rightTreeHigh + 1, diameter);
        return std::max(leftTreeHigh, rightTreeHigh) + 1;
    }

    int diameterOfBinaryTree(TreeNode *root)
    {
        maxDepth(root);
        return diameter - 1; // 左右子树重复计算
    }
};
// @lc code=end

/**
 * [4,-7,-3,null,null,-9,-3 ,9,-7,-4,null,6,null,-6,-6,null,null,0,6,5,null,9,null,null,-1,-4,null,null,null,-2]
 *
 *                                     4,
 *                  -7,                                            -3,
 *          null,          null,                          -9,                     -3,
 *                                               9,              -7,         -4,         null,
 *                                           6,    null     -6,      -6,  null,null,
 *                                       0,     6,         5,null,  9,null,
 *                                   null,-1, -4,null, null,null, -2
 */